package mashibing.class2;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 一个数组中有一种数出现K次，其他数都出现了M次，
 * M > 1,  K < M
 * 找到，出现了K次的数，
 * 要求，额外空间复杂度O(1)，时间复杂度O(N)
 *
 * @author yujiafan
 * @version 1.0.0
 * @create 2023-03-08
 */
public class Class2_3_KM {

    public static int test(int[] arr, int k, int m) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : arr) {
            if (!map.containsKey(num)) {
                map.put(num, 1);
            } else {
                map.put(num, map.get(num) + 1);
            }
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            Integer value = entry.getValue();
            if (value.equals(k)) {
                return entry.getKey();
            }
        }
        return -1;
    }

    public static KM generateArrays() {
        KM km = new KM();
        // k、m出现次数1-5
        int k = (int) (Math.random() * 8) + 1;
        int m = (int) (Math.random() * 8) + 2;
        while (k >= m) {
            m = (int) (Math.random() * 8) + 2;
        }
        // m数量  1-9
        int mCount = (int) (Math.random() * 5) + 1;

        int[] arr = new int[k + m * mCount];
        int index = 0;
        // 插入k的值
        int kValue = (int) (Math.random() * 10);
        for (; index < k; index++) {
            arr[index] = kValue;
        }
        // 插入m的值
        for (; index < arr.length; ) {
            int mValue = (int) (Math.random() * 10);
            while (kValue == mValue){
                mValue = (int) (Math.random() * 10);
            }
            for (int i = 0; i < m; i++) {
                arr[index++] = mValue;
            }
        }
        // 打乱顺序
        for (int i = 0; i < arr.length; i++) {
            int swapIndex = (int) (Math.random() * arr.length);
            int temp = arr[i];
            arr[i] = arr[swapIndex];
            arr[swapIndex] = temp;
        }
        km.setK(k);
        km.setM(m);
        km.setArr(arr);
        return km;
    }

    public static int findKNum(int[] arr, int k, int m) {
        int[] help = new int[32];
        int ans = 0;
        for (int num : arr) {
            for (int i = 0; i < 32; i++) {
                help[i] += (num >> i) & 1;
            }
        }
        for (int i = 0; i < 32; i++) {
            if (help[i] % m != 0) {
                ans |= 1 << i;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
//        int k = 2, m = 3;
//        int[] arr = {2, 3, 3, 3, 2, 1, 1, 1, 8, 8, 8};
//        System.out.println(findKNum(arr, k, m));
//        System.out.println(test(arr, k, m));

        // 对数器
        System.out.println("测试开始");
        boolean flag = true;
        int testCount = 10000;
        for (int i = 0; i < testCount; i++) {
            KM km = generateArrays();
            int k1 = test(km.getArr(), km.getK(), km.getM());
            int k2 = findKNum(km.getArr(), km.getK(), km.getM());
            if (k1 != k2) {
                System.out.println("K=" + km.getK() + ",m=" + km.getM());
                System.out.println(Arrays.toString(km.getArr()));
                System.out.println("答案：" + k1 + "--------" + k2);
                System.out.println("出错了");
                flag = false;
                break;
            }
        }
        if(flag){
            System.out.println("测试通过");
        } else {
            System.out.println("测试失败");
        }


//        int[] error = {7, 0, 5, 0, 6, 0, 4, 1, 5, 1, 1, 7, 2, 2, 9, 5, 4, 3, 4, 1, 8, 6, 5, 8, 5, 1, 2, 9, 4, 2, 5, 8, 8, 0};
//        System.out.println(Arrays.toString(error));
//        System.out.println(findKNum(error, 2, 4));
//        System.out.println(test(error, 2, 4));
//        Arrays.sort(error);
//        System.out.println(Arrays.toString(error));
    }
}
